《算法竞赛入门经典》 第4章-函数与程序结构

发表于 | 分类于

基础知识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 计算两点之间的欧几里德的距离
double dist(double x1, double x2, double y1, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double dist_1(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return hypot(dx, dy);
}

struct Point {
    double x, y;
};

double dist_2(struct Point a, struct Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}

typedef struct {
    double x, y;
}Point_;

double dist_3(Point_ a, Point_ b) {
    return hypot(a.x - b.x, a.y - b.y);
}
1
2
3
4
5
6
7
8
9
10
11
12
// 4.1 组合数（有BUG，中间变量可能会溢出）
long long factorial(int n) {
    long long m = 1;
    for (int i = 1; i <= n; i++) {
        m *= i;
    }
    return m;
}

long long C(int n, int m) {
    return factorial(n) / (factorial(m) * factorial(n - m));
}
1
2
3
4
5
6
7
8
// 4.1 组合数
long long C(int n, int m) {
    if (m < n - m) m = n - m;
    long long ans = 1;
    for (int i = m + 1; i <= n; i++) ans *= i;
    for (int i = 1; i <= n - m; i++) ans /= i;
    return ans;
}
1
2
3
4
5
6
7
// 4.2 素数判定 （有问题）
int is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

1会被误判为素数，当n太大的时候，当n为接近int最大值的素数时候，i*i有可能会发生溢出。

1
2
3
4
5
6
7
8
9
// 4.2 素数判定
int is_prime_1(int n) {
    if (n <= 1) return 0;
    int m = floor(sqrt(n) + 0.5);
    for (int i = 2; i <= m, i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

避免了重复计算sqrt(n)，同时+0.5避免了xxx.99999出现后取整的误差。

1
2
3
4
5
6
7
8
9
// 4.3 用函数交换变量（错误）
void swap(int a, int b) {
    int t = a; a = b; b = t;
}

    int a, b;
    a = 3; b = 4;
    swap(3, 4);
    printf("a: %d b: %d\n", a, b);

同理，试了下，java也是不行的。

1
2
3
4
5
6
7
8
9
10
11
public static void swap(int a, int b) {
    int t = a;
    a = b;
    b = t;
}

public static void main(String[] args) {
    int a = 3, b = 4;
    swap(a, b);
    System.out.printf("a = %d, b = %d.", a, b);
}

1
2
3
4
5
6
7
8
9
10
// 4.3 用函数交换变量
void swap(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

    int a =3, b = 4;
    swap(&a, &b);
    printf("a = %d, b = %d\n", a, b);

a = 4, b = 3

Q：递归和迭代到底是什么关系？

1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算数组的元素和（错误，PS：C++中是可行的，亲测）
int sum(int a[]) {
    int ans = 0;
    for (int i = 0; i < sizeof(a); i++) {
        ans += a[i];
    }
    return ans;
}

    int a[] = {1,2,3};
    printf("%d\n", sum(a));
    
6(C++测得)

新建了个c项目测试了下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int sum(int a[]) {
    int ans = 0;
    for (int i = 0; i < sizeof(a); i++) {
        ans += a[i];
    }
    return ans;
}

int main() {
    int a[] = {1,2,3};
    printf("%d\n", sum(a));
    return 0;
}

D:\Markdown\Coding\C\Exercises\main.c: In function 'sum':
D:\Markdown\Coding\C\Exercises\main.c:5:31: warning: 'sizeof' on array function parameter 'a' will return size of 'int *' [-Wsizeof-array-argument]
     for (int i = 0; i < sizeof(a); i++) {
                               ^
D:\Markdown\Coding\C\Exercises\main.c:3:13: note: declared here
 int sum(int a[]) {

修改后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

int sum(int* a, int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    return ans;
}

int main() {
    int a[] = {1,2,3};
    printf("%d\n", sum(a + 1, 2));
    return 0;
}

5

回到c++的环境中来：c可以的c++一定可以嘛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 计算数组的元素和（正确）
int sum(int* a, int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i];
    }
    return ans;
}

    int a[] = {1,2,3};
    printf("%d\n", sum(a + 1, 2));
    return 0;

5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 计算左闭右开区间的元素和（两种写法）
// 方法一
int sum(int* begin, int* end) {
    int n = end - begin;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += begin[i];
    }
    return ans;
}

// 方法二
int sum(int* begin, int* end) {
    int *p = begin;
    int ans = 0;
    for (int *p = begin; p != end; p++) {
        ans += *p;
    }
    return ans;
}

暂时掠过：函数做参数。道理明白，题先放着。

1
2
3
4
// 用递归计算阶乘
int f(int n){
    return n == 0 ? 1 : f(n - 1) * n;
};

记住，调用自己和调用其他函数没有什么本质不同。

4-1 UVa1339 Ancient Cipher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
  char s1[200], s2[200];
  while(scanf("%s%s", s1, s2) == 2) {
    int n = strlen(s1);
    int cnt1[26] = {0}, cnt2[26] = {0};
    for(int i = 0; i < n; i++) cnt1[s1[i] - 'A']++;
    for(int i = 0; i < n; i++) cnt2[s2[i] - 'A']++;
    sort(cnt1, cnt1 + 26);
    sort(cnt2, cnt2 + 26);
    int ok = 1;
    for(int i = 0; i < 26; i++)
      if(cnt1[i] != cnt2[i]) ok = 0;
    if(ok) printf("YES\n"); else printf("NO\n");
  }
  return 0;
}


JWPUDJSTVP
VICTORIOUS

YES

4-2 UVa489 Hangman Judge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

#define maxn 105
int Left, Chance; // 还要猜left个位置，错chance次后就会输
char s[maxn], s1[maxn];
int win, lose;

void guess(char ch) {
    int bad = 1;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == ch) { Left--; s[i] = ' '; bad = 0; }
    }
    if (bad) Chance--;
    if (!Chance) lose = 1;
    if (!Left) win = 1;
}

int main() {
    int rnd;
    while (scanf("%d%s%s", &rnd, s, s1) == 3 && rnd != -1) {
        printf("Round %d\n", rnd);
        win = lose = 0;
        Left = strlen(s);
        Chance = 7;
        for (int i = 0; i < strlen(s1); i++) {
            guess(s1[i]);
            if (win || lose) break;
        }
        if (win) printf("You win.\n");
        else if (lose) printf("You lose.\n");
        else printf("You chickened out.\n");
    }

    return 0;
}

4-3 UVa133 The Dole Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

#define maxn 25
int n, m, k, cell[maxn];

int go(int p, int d, int t) {
    while (t--) {
        do {
            p = (p + d + n - 1) % n + 1;
        } while (cell[p] == 0);
    }
    return p;
}

int main() {
    while (scanf("%d%d%d", &n, &k, &m) == 3 && n) {
        for (int i = 1; i <= n; i++) cell[i] = i;
        int left = n;
        int p1 = n, p2 = 1;
        while (left) {
            p1 = go(p1, 1, k);
            p2 = go(p2, -1, m);
            printf("%3d", p1); left--;
            if (p2 != p1) { printf("%3d", p2); left--; }
            cell[p1] = cell[p2] = 0;
            if (left) printf(",");
        }
        printf("\n");
    }

    return 0;
}

4-4 UVa213 Message Decoding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

int readchar() { // 实现跨行读字符
    for (; ;) {
        int ch = getchar();
        if (ch != '\n' && ch != '\r') return ch;
    }
}

int readint(int c) { // 读取c位的二进制符，并转换为十进制
    int v = 0;
    while (c--) v = v * 2 + readchar() - '0';
    return v;
}

int code[8][1<<8]; // 把1左移8位，相当于1×2^8，等于256

int readcode() { // 读取编码
    memset(code, 0, sizeof(code));
    code[1][0] = readchar();
    for (int len = 2; len < 8; len++) {
        for (int i = 0; i < (1<<len) - 1; i++) {
            int ch = getchar();
            if (ch == EOF) return 0;
            if (ch == '\n' || ch == '\r') return 1;
            code[len][i] = ch;
        }
    }
    return 1;
}

int main() {
    while (readcode()) {
        for (; ;) {
            int len = readint(3);
            if (len == 0) break;
            for (; ;) {
                int v = readint(len);
                if (v == (1 << len) - 1) break;
                putchar(code[len][v]);
            }
        }
        printf("\n");
    }

    return 0;
}

TNM AEIOU
0010101100011
1010001001110110011
11000

TAN ME

4-5 UVa512 Spreadsheet Tracking (A)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// UVa512 Spreadsheet Tracking (算法1)
// Rujia Liu
#include<stdio.h>
#include<string.h>
#define maxd 100
#define BIG 10000
int r, c, n, d[maxd][maxd], d2[maxd][maxd], ans[maxd][maxd], cols[maxd];

void copy(char type, int p, int q) {
  if(type == 'R') {
    for(int i = 1; i <= c; i++)
      d[p][i] = d2[q][i];
  } else {
    for(int i = 1; i <= r; i++)
      d[i][p] = d2[i][q];
  }
}

void del(char type) {
  memcpy(d2, d, sizeof(d));
  int cnt = type == 'R' ? r : c, cnt2 = 0;
  for(int i = 1; i <= cnt; i++) {
    if(!cols[i]) copy(type, ++cnt2, i);
  }
  if(type == 'R') r = cnt2; else c = cnt2;
}

void ins(char type) {
  memcpy(d2, d, sizeof(d));
  int cnt = type == 'R' ? r : c, cnt2 = 0;
  for(int i = 1; i <= cnt; i++) {
    if(cols[i]) copy(type, ++cnt2, 0);
    copy(type, ++cnt2, i);
  }
  if(type == 'R') r = cnt2; else c = cnt2;
}

int main() {
  int r1, c1, r2, c2, q, kase = 0;
  char cmd[10];
  memset(d, 0, sizeof(d));
  while(scanf("%d%d%d", &r, &c, &n) == 3 && r) {
    int r0 = r, c0 = c;
    for(int i = 1; i <= r; i++)
      for(int j = 1; j <= c; j++)
        d[i][j] = i*BIG + j;
    while(n--) {
      scanf("%s", cmd);
      if(cmd[0] == 'E') {
        scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
        int t = d[r1][c1]; d[r1][c1] = d[r2][c2]; d[r2][c2] = t;
      } else {
        int a, x;
        scanf("%d", &a);
        memset(cols, 0, sizeof(cols));
        for(int i = 0; i < a; i++) { scanf("%d", &x); cols[x] = 1; }
        if(cmd[0] == 'D') del(cmd[1]); else ins(cmd[1]);
      }
    }
    memset(ans, 0, sizeof(ans));
    for(int i = 1; i <= r; i++)
      for(int j = 1; j <= c; j++) {
        ans[d[i][j]/BIG][d[i][j]%BIG] = i*BIG+j;
      }
    if(kase > 0) printf("\n");
    printf("Spreadsheet #%d\n", ++kase);

    scanf("%d", &q);
    while(q--) {
      scanf("%d%d", &r1, &c1);
      printf("Cell data in (%d,%d) ", r1, c1);
      if(ans[r1][c1] == 0) printf("GONE\n");
      else printf("moved to (%d,%d)\n", ans[r1][c1]/BIG, ans[r1][c1]%BIG);
    }
  }
  return 0;
}

7 9
5
DR 2 1 5
DC 4 3 6 7 9
IC 1 3
IR 2 2 4
EX 1 2 6 5
4
4 8
5 5
7 8
6 5
0 0

Spreadsheet #1
Cell data in (4,8) moved to (4,6)
Cell data in (5,5) GONE
Cell data in (7,8) moved to (7,6)
Cell data in (6,5) moved to (1,2)

# 4-5 UVa512 Spreadsheet Tracking (B)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// UVa512 Spreadsheet Tracking (算法2)
// Rujia Liu
#include<stdio.h>
#include<string.h>
#define maxd 10000

struct Command {
  char c[5];
  int r1, c1, r2, c2;
  int a, x[20];
} cmd[maxd];
int r, c, n;

int simulate(int* r0, int* c0) {
  for(int i = 0; i < n; i++) {
    if(cmd[i].c[0] == 'E') {
       if(cmd[i].r1 == *r0 && cmd[i].c1 == *c0) { *r0 = cmd[i].r2; *c0 = cmd[i].c2; }
       else if(cmd[i].r2 == *r0 && cmd[i].c2 == *c0) { *r0 = cmd[i].r1; *c0 = cmd[i].c1; }
    } else {
      int dr = 0, dc = 0;
      for(int j = 0; j < cmd[i].a; j++) {
        int x = cmd[i].x[j];
        if(cmd[i].c[0] == 'I') {
          if(cmd[i].c[1] == 'R' && x <= *r0) dr++;
          if(cmd[i].c[1] == 'C' && x <= *c0) dc++;
        }
        else {
          if(cmd[i].c[1] == 'R' && x == *r0) return 0;
          if(cmd[i].c[1] == 'C' && x == *c0) return 0;
          if(cmd[i].c[1] == 'R' && x < *r0) dr--;
          if(cmd[i].c[1] == 'C' && x < *c0) dc--;
        }
      }
      *r0 += dr; *c0 += dc;      
    }
  }
  return 1;
}

int main() {
  int r0, c0, q, kase = 0;
  while(scanf("%d%d%d", &r, &c, &n) == 3 && r) {
    for(int i = 0; i < n; i++) {
      scanf("%s", cmd[i].c);
      if(cmd[i].c[0] == 'E') {
        scanf("%d%d%d%d", &cmd[i].r1, &cmd[i].c1, &cmd[i].r2, &cmd[i].c2);
      } else {
        scanf("%d", &cmd[i].a);
        for(int j = 0; j < cmd[i].a; j++) scanf("%d", &cmd[i].x[j]);
      }
    }
    if(kase > 0) printf("\n");
    printf("Spreadsheet #%d\n", ++kase);

    scanf("%d", &q);
    while(q--) {
      scanf("%d%d", &r0, &c0);
      printf("Cell data in (%d,%d) ", r0, c0);
      if(!simulate(&r0, &c0)) printf("GONE\n");
      else printf("moved to (%d,%d)\n", r0, c0);
    }
  }
  return 0;
}

4-6 UVa12412 A Typical Homework

1
2


1
2
3
4
5
6
7
int main() {
    freopen("D:\\Markdown\\Coding\\C++\\temporary\\in.txt", "r", stdin);
    freopen("D:\\Markdown\\Coding\\C++\\temporary\\out.txt", "w", stdout);

    fclose(stdin);
    fclose(stdout);
}